-- 广度优先搜索可解决两类问题
--   从节点 A 出发，有前往节点 B 的路径吗 
--   从节点 A 触发，前往节点 B 的哪条路径最短
local Queue = {}
Queue.__index = Queue

function Queue:push(val)
    table.insert(self.array, val)
end

function Queue:pop()
    return table.remove(self.array, 1)
end

function Queue:is_empty()
    return #self.array == 0
end

function Queue:init(...)
    self.array = {...}
end

local function _new_queue(...)
    local q = setmetatable({}, Queue)
    q:init(...)
    return q
end

local function _is_seller(name)
    return string.char(string.byte(name, -1)) == "m"
end

local function _build_graph()
    local graph = {
        you = {"alice", "bob", "claire"},
        bob = {"anuj", "peggy"},
        alice = {"peggy"},
        claire = {"thom", "jonny"},
        anuj = {},
        peggy = {},
        thom = {},
        jonny = {},
    }

    -- Debug check
    for _, v in pairs(graph) do
        for _, name in ipairs(v) do
            assert(graph[name])
        end
    end

    return graph
end

local function _breadth_first_search(graph, start)
    local val = assert(graph[start])
    local search_queue = _new_queue(table.unpack(val))
    local searched = {}
    while not search_queue:is_empty() do
        local name = search_queue:pop()
        if not searched[name] then
            searched[name] = true

            if _is_seller(name) then
                return name
            end

            for _, v in ipairs(graph[name]) do
                search_queue:push(v)
            end
        end
    end
    return false
end

local function test()
    local graph = _build_graph()
    local name = _breadth_first_search(graph, "you")
    assert(name == "thom", name)
end

test()

